package sortutil

func HeapSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	for i := range arr {
		heapInsert(arr, i)
	}
	heapSize := len(arr)
	for heapSize > 0 {
		heapify(arr, heapSize)
		heapSize--
		arr[0], arr[heapSize] = arr[heapSize], arr[0]
	}
}

func heapify(arr []int, size int) {
	index := 0
	left := index*2 + 1
	for left < size {
		largest := left
		if left+1 < size && arr[left+1] > arr[left] {
			largest = left + 1
		}
		if arr[largest] < arr[index] {
			largest = index
			break
		} else {
			arr[largest], arr[index] = arr[index], arr[largest]
			index = largest
			left = index*2 + 1
		}
	}
}

func heapInsert(arr []int, i int) {
	for arr[i] > arr[(i-1)/2] {
		arr[i], arr[(i-1)/2] = arr[(i-1)/2], arr[i]
		i = (i - 1) / 2
	}
}
